package bit;

/**题目：求二进制位1的个数
 * @Author Gavin
 * @date 2022.01.02 22:23
 */
public class bit_3 {
    /**
     * 第一种方法：
     * 使用一个掩码 1 和数字进行与运算，然后定义一个计数器
     * 每进行一次与运算 掩码向左移动一位
     */
    //Time:O(m) Space:O(1)
    public static int solution_1(int n){
        int mask=1,count=0;
        int t=0;
        while (mask!=0){
            /**
             * 如12举例
             * 第一次n:  1 1 0 0
             *   mask :        1   初始为1
             *  result:        0
             *  第二次n: 1 1 0 0
             *   mask:       1 0   掩码左移动1位
             *  result:      0 0
             *  第三次n: 1 1 0 0
             *   mask:     1 0 0
             *  result:    1 0 0  不为0了，符合条件
             */
            if((n&mask)!=0)++count;
            mask<<=1;//移动32位就变为0
            t++;
        }
        System.out.println(t);
        return count;
    }
    //Time:O(k) Space:O(1)
    public int solution_2(int n){
        int count=0;
        while (n!=0){
            ++count;
            n&=(n-1);//该操作每次可以消除低位的1
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(solution_1(12));
    }
}
